package com.test;

import java.util.LinkedList;

public class MaxWindowSliding {
    public static void main(String[] args) {
        int[] nums = {1, 3, 1, 2, 0, 5};
        int k = 3;
        System.out.println(MaxSlidingWindow.printArray(getMaxWindowSliding(nums, k)));
    }

    /**
     * 核心在于cache，每次添加一个值，必然先把小于当前值的index全部清空，这样能保证cache的第一个值对应到数组里的值一定是最大的；
     * 每次添加一个值，要remove掉失效的（超出窗口最大值）
     */
    public static int[] getMaxWindowSliding(int[] array, int windowSize) {
        if (array == null || windowSize <= 0 || array.length < windowSize) return new int[0];
        int[] result = new int[array.length - windowSize + 1];

        LinkedList<Integer> bigValueIndexCache = new LinkedList<>();
        for (int i = 0; i < array.length; i++) {
            while (!bigValueIndexCache.isEmpty() && array[bigValueIndexCache.peekLast()] < array[i]) {
                bigValueIndexCache.removeLast();
            }
            bigValueIndexCache.addLast(i);

            if (i - bigValueIndexCache.peekFirst() >= windowSize) {
                bigValueIndexCache.removeFirst();
            }

            if (i - windowSize + 1 >= 0) {
                result[i + 1 - windowSize] = array[bigValueIndexCache.peekFirst()];
            }
        }
        return result;
    }
}
